package org.yanse.structures.linkedList;

public class DoublyLinkedList {
        private DoublyListNode head;
        private DoublyListNode tail;
        private int size;

        public DoublyLinkedList() {
            head = null;
            tail = null;
        }

        public DoublyLinkedList(int[] arrays) {
            if (arrays == null || arrays.length == 0) {
                head = null;
                tail = null;
                size = 0;
                return;
            }
            head = new DoublyListNode(arrays[0]);
            DoublyListNode current = head;
            DoublyListNode lastNode = null;
            for (int i = 1; i < arrays.length; i++) {
                current.next = new DoublyListNode(arrays[i]);
                current.last = lastNode;
                lastNode = current;
                current = current.next;
            }
            tail = current;
            tail.last = lastNode;
            size = arrays.length;
        }

        public void printLinkedList() {
            if (size == 0) {
                return;
            }
            DoublyListNode current = head;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
        }

        public void reversePrintLinkedList() {
            if (size == 0) {
                return;
            }
            DoublyListNode current = tail;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.last;
            }
        }

        public void addFirst(int ele) {
            DoublyListNode eleNode = new DoublyListNode(ele);
            if (head == null) {
                head = eleNode;
                tail = head;
                size = 1;
                return;
            }
            head.last = eleNode;
            eleNode.next = head;
            head = eleNode;
            size++;
        }

        public void addLast(int ele) {
            DoublyListNode eleNode = new DoublyListNode(ele);
            if (head == null) {
                head = eleNode;
                tail = head;
                size = 1;
                return;
            }

            tail.next = eleNode;
            eleNode.last = tail;
            tail = eleNode;
            size++;
        }

        // public void add(int index, int ele) {
        //     if (index <= 0) {
        //         addFirst(ele);
        //         return;
        //     }
        //     if (index >= size - 1) {
        //         addLast(ele);
        //         return;
        //     }
            
        //     DoublyListNode eleNode = new DoublyListNode(ele);
        //     int currentIndex = 0;
        //     DoublyListNode current = head;
        //     while (current != null) {
        //         if (currentIndex == index) {
        //             current.last.next = eleNode;
        //             eleNode.last = current.last;
        //             eleNode.next = current;
        //             current.last = eleNode;
        //             size++;
        //             return;
        //         }
        //         currentIndex++;
        //         current = current.next;
        //     }
        // }

        public void add(int index, int ele) {
            if (index <= 0) {
                addFirst();
                return;
            }

            if (index >= size - 1) {
                addLast();
                return;
            }


            DoublyListNode indexNode = getNode(index);
            DoublyListNode eleNode = new DoublyListNode(ele);
            indexNode.last.next = eleNode;
            eleNode.last = indexNode.last;
            eleNode.next = indexNode;
            current.last = eleNode;
            size++;
        }

        public void set(int index, int ele) {
            getNode(index).val = ele;
        }

        // public void set(int index, int ele) {
        //     if (size == 0) {
        //         throw new NoSuchElementException("linked list is empty");
        //     }
        //     if (index <= 0) {
        //         head.val = ele;
        //         return;
        //     }
        //     if (index >= size - 1) {
        //         tail.val = ele;
        //         return;
        //     }
        //     int currentIndex = 0;
        //     DoublyListNode current = head;
        //     while (current != null) {
        //         if (currentIndex == index) {
        //             current.val = ele;
        //             return;
        //         }
        //         currentIndex++;
        //         current = current.next;
        //     }
        // }
        private DoublyListNode getNode(int index) {
            if (size == 0) {
                throw new NoSuchElementException("linked list is empty");
            }
            if (index <= 0) {
                return head;
            }
            if (index >= size - 1) {
                return tail;
            }

            int currentIndex = 0;
            if (index < size / 2) {
                DoublyListNode current = head;
                while (current != null) {
                    if (currentIndex == index) {
                        return current;
                    }
                    currentIndex++;
                    current = current.next;
                }
            } ele {
                DoublyListNode current = tail;
                while (current != null) {
                    if (currentIndex == index) {
                        return current;
                    }
                    currentIndex++;
                    current = current.last;
                }
            }
            throw new NoSuchElementException();
        }

        // public int getFirst() {
        //     if (size == 0) {
        //         throw new NoSuchElementException("linked list is empty");
        //     }
        //     return head.val;
        // }

        public int getFirst() {
            return getNode(0);
        } 

        // public int getLast() {
        //     if (size == 0) {
        //         throw new NoSuchElementException("linked list is empty");
        //     }
        //     return tail.val;
        // }

        public int getLast() {
            return getNode(size -1);
        }

        // public int get(int index) {
        //     if (index <= 0) {
        //         return getFirst();
        //     }
        //     if (index >= size - 1) {
        //         return getLast();
        //     }

        //     int currentIndex = 0;
        //     DoublyListNode current = head;
        //     while (current != null) {
        //         if (currentIndex == index) {
        //             return current.val;
        //         }
        //         currentIndex++;
        //         current = current.next;
        //     }
        //     return 0;
        // }

        public int get(int index) {
            return getNode(index).val;
        }

        public void removeFirst() {
            if (size == 0) {
                throw new NoSuchElementException("linked list is empty");
            }
            head = head.next;
            if (head != null) {
                head.last = null;
            }
            if (size < 3) {
                tail = head;
            }
            size--;
        }

        public void removeLast() {
            if (size == 0) {
                throw new NoSuchElementException("linked list is empty");
            }
            tail = tail.last;
            if (tail != null) {
                tail.next = null;
            }

            if (size < 3) {
                head = tail;
            }
            size--;
        }

        // public void remove(int index) {
        //     if (index <= 0) {
        //         removeFirst();
        //         return;
        //     }

        //     if (index >= size - 1) {
        //         removeLast();
        //         return;
        //     }

        //     int currentIndex = 0;
        //     DoublyListNode current = head;
        //     while (current != null) {
        //         if (currentIndex == index) {
        //             current.last.next = current.next;
        //             current.next.last = current.last;
        //             size--;
        //             return;
        //         }
        //         current = current.next;
        //         currentIndex++;
        //     }
        // }

        public void remove(int index) {
            if (index <= 0) {
                removeFirst();
                return;
            }

            if (index >= size - 1) {
                removeLast();
                return;
            }

            DoublyListNode current = getNode(index);
            current.last.next = current.next;
            current.next.last = current.last;
            size--;
        }

        public int size() {
            return size;
        }

        public void reverse() {
            if (size < 2) {
                return;
            }
            DoublyListNode current = head;
            DoublyListNode lastNode = null;
            DoublyListNode nextNode = null;
            tail = current;
            while (current != null) {
                lastNode = current.last;
                nextNode = current.next;
                current.last = nextNode;
                current.next = lastNode;
                if (nextNode == null) {
                    head = current;
                }
                current = nextNode;
            }
        }
}
